A collection of counting techniques
Speeding up the process by equating states
Conditions that can be summarized
Same destination state
The coefficients on the transitions are the same.
All of the summarized states either meet or do not meet the conditions of the problem statement.
When determining permutations in DP, it is necessary to keep track of "what has already been used".
If it is small, you can use bit DP. Instead of doing it in order, do it in ascending/descending order of what you put in.
5 Return from greedy
Find the number of columns that may be created by an operation" is difficult when the same column is created by multiple operation columns
It would be easier to count if there was a way to uniquely determine the operation sequence from the product.
6 Techniques for Case Segregation
Case by parameter
Be careful to DISJOINT
Predicting the number of invariants
If it's even, it's likely to have even-odd invariants.
9 Use of recursive definitions
10 About [Digit DP
11 Acceleration Techniques
11.1 Using [cumulative sum
11.2 Use of Data Structures
11.3 Array usage
Can be used for operations that satisfy the coupling and exchange laws
Algorithm similar to [Fast Fourier Transform
11.7 Simple branch trimming
12 Techniques with Matrices 26
Power of the companion matrix
Power of polynomial
12.2 Matrix Expression Techniques
14 Binomial coefficient technique 30
14.1 Collection of frequently used formulas
14.2 Return to [Number of routes
Attributing binomial coefficients to the number of paths makes it easy to transform the equation
15.1 When symmetry is used
15.2 Using DP
16 Identifying "unsolvable problems
---
This page is auto-translated from /nishio/数え上げテクニック集 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.